package com.lsa.letcode.the82.deleteDuplicates2;

import java.util.ArrayList;
import java.util.List;

import com.lsa.letcode.common.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 
 * 1 - 1 - 1 - 2 - 3 => 2 - 3
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
    	if (head == null) {
    		return null;
    	}
    	    	
    	ListNode n = head.next; // n is first el s.t (n == null OR n.val != head.val)
    	while(n != null && n.val == head.val){
    		n = n.next;
    	}
    	
    	ListNode noDupes = deleteDuplicates(n);
		if (head.next != n) { // if head.next != n => head is duplicated, new head is needed
    		head = noDupes;
    	}
    	else { // n == head.next. Head is OK, just remove duplicates from its next
    		head.next = noDupes;
    	}
    	
    	return head;
    }
    
    /**
     * No recursive calls.
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2(ListNode head) {
    	class StackEl {
    		ListNode head;
    		ListNode n;
    		boolean isCalled; // false - find m, call; true - called
			public StackEl(ListNode head) {
				this.head = head;
			}
    	}
    	
    	List<StackEl> stack = new ArrayList<StackEl>();
    	stack.add(new StackEl(head));
    	
    	ListNode result = null;
    	while(!stack.isEmpty()) {
    		StackEl frame = stack.get(stack.size() - 1); // peek
    		if (!frame.isCalled) {
    			if (frame.head == null) {
    				result = null;
    				stack.remove(stack.size() - 1);
    				continue;
    			}
    			ListNode n = frame.head.next; // n is first el s.t (n == null OR n.val != head.val)
    	    	while(n != null && n.val == frame.head.val){
    	    		n = n.next;
    	    	}
    	    	frame.n = n;
    	    	stack.add(new StackEl(n));
    	    	frame.isCalled = true;
    		}
    		else {
    			if (frame.head.next != frame.n) { // if head.next != n => head is duplicated, new head is needed
    				frame.head = result;
    	    	}
    	    	else { // n == head.next. Head is OK, just remove duplicates from its next
    	    		frame.head.next = result;
    	    	}
    			result = frame.head;
    			stack.remove(stack.size() - 1);
    		}
    	}
    	
    	return result;
    }
}